package my.algorithms.mcorrea.sorting;

/**
 *
 * @author mcorrea
 */
public class SortingAlgorithms {

    public static void main(String[] args) {
		countSort( new int[]{2,5,3,0,2,3,0,3},  6 );
		countSort( new int[]{1,5,6,2,7,4,3,1,2,6},  8 );
		
		insertionSort(new int[]{2, 1, 3, 9, 6, 5, 0});
		insertionSort(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0 });//worst case
		
		bubbleSort(new int[]{2, 1, 3, 9, 6, 5, 0});
		bubbleSort(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0 });
		System.out.println("Merge sort");
		
		int A[] = mergeSort(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }, 0 , 9);
		for(int x: A){
			System.out.print(x+ " ");
		}
		System.out.println();
		
    }
	
	
	// O(n)
	public static int[] countSort(int A[], int k){
		int B[] = new int[A.length]; //sorted array B
		int C[] = new int[k];
		//first step set all C to 0. This is done by java by default but for completeness it is done here
		for(int i=0; i<C.length; i++){
			C[i] = 0;
		}
		//now count the elements in A and store it to C
		for(int i=0; i<A.length; i++){
			C[A[i]] = C[A[i]] +1;
		}
		//add with previous to know the spaces in where the number will go
		for(int i=1; i<C.length; i++){
			C[i] += C[i-1];
		}
		//extra step to coodinate the indexes. starting from 0 to A.lenght-1
		for(int i=0; i<C.length; i++){
			C[i]--;
		}
		//now put the number in order in B
		for(int i=A.length-1; i>=0; i--){
			B[ C[A[i]] ] = A[i];
			C[A[i]] -=1;
		}
		
		for(int x: B){
			System.out.print(x+" ");
		}
		System.out.println();
		return B;
	}
	
	//O(n^2)
	public static int[] insertionSort(int A[]){
		
		for(int j=1; j<A.length; j++){
			int key = A[j];
			int i = j-1;
			while( i>=0 && A[i]>key ){
				A[i+1] = A[i];
				i = i-1;
			}
			 A[i+1] = key;
		}
		
		for(int x: A){
			System.out.print(x+" ");
		}
		System.out.println();
	
		return A;
	}
	
	//O(n^2) naive algorithm
	public static int[] bubbleSort(int A[]){
		boolean swapped;
		do{
			swapped = false;
			for(int k=1; k<A.length; k++){
				if(A[k] < A[k-1]){
					int temp = A[k];
					A[k] = A[k-1];
					A[k-1] = temp;
					swapped = true;
				}
			}	
		}while(swapped);
		
		
		for(int x: A){
			System.out.print(x+" ");
		}
		System.out.println();
		
	
		return A;
	}

	//O(nlogn)
	public static int[] mergeSort(int A[], int p, int r){
		if(p < r){
			int q = (int)(p+r)/2; //this will alwasy give us the floor
			mergeSort(A, p, q);
			mergeSort(A, q+1, r);
			merge(A, p, q, r);
		}
		
		
		return A;
	}
	
	public static void merge(int A[], int p, int q, int r){
		int n1 = q-p+1;
		int n2 = r-q;
		Integer L[] = new Integer[n1+1];
		Integer R[] = new Integer[n2+1];
		//copy left
		for(int i=0; i<n1; i++){
			L[i] = A[p+i];
		}
		//copy right
		for(int j=0;j<n2;j++){
			R[j] = A[q+j+1];
		}
		
		L[n1] = null;
		R[n2] = null;
		
		int i=0;
		int j=0;
		for(int k=p; k<=r; k++){
				if( ((L[i]==null && R[j]==null) || (L[i]!=null && R[j]==null)) &&
						 L[i]<= R[j]){
					A[k] = L[i];
					i++;
				}else{
					A[k] = R[j];
					j++;
				} 
			}
	}
	
	
	
	//O(nlgn)
	public static int[] quicksort(int A[], int p, int r){
		return A;
	}
	
	public static int partition(int A[], int p, int r){
		return 0;
	}
	
	
}
